package org.ala.tree.avl;

import java.util.Comparator;
import java.util.LinkedList;

import org.ala.tree.AbstractTree;

/**
 * 直接二叉搜索树，在原本数据就有序（或部分有序）的情况下，会退化为链表
 * 那么解决的办法就是在插入/删除时，手动调整树结构，让其节点分布”尽量均匀“
 * 
 * AVL树：每个节点的左右子树高度差只在[-1,1]范围内
 * 	定义平衡因子：左子树高度 - 右子树高度。允许的平衡因子取值范围：[-1, 0, 1]
 * 在插入或删除时，通过旋转来实现树结构调整：
 * 插入：
 * 	如果插入后，节点平衡因子=-2（失衡），左子树平衡因子=-1，说明失衡来自左子树的左子树，对节点进行右旋
 * 	如果插入后，节点平衡因子=-2（失衡），左子树平衡因子=1，说明失衡来自左子树的右子树，先对左子树左旋，在对节点右旋
 * 	如果插入后，节点平衡因子=2（失衡），右子树平衡因子=1，说明失衡来自右子树的右子树，对节点左旋
 * 	如果插入后，节点苹果因子=2（失衡），右子树的平衡因子=-1，说明失衡来自右子树的左子树，先对右子树右旋，在对节点左旋
 * 删除：
 * 	如果删除后，父节点的平衡因子=-2（失衡，且是因为删除右节点，导致的左子树带来失衡），进一步判断左子树
 * 		若左子树平衡因子 <= 0，说明是左子树的左子树高了，父节点右旋
 * 		若左子树平衡因子 > 0，说明是左子树的右子树高了，左子树先左旋，父节点再右旋
 * 		继续探测父节点是否失衡
 * 	如果删除后，父节点的平衡因子=2（失衡，原因和处理方式与-2的情况刚好对称）
 *  如果删除后，父节点的平衡因子=-1，说明之前是平衡的，现在也是平衡的，且高度差没变化，可以停止继续往上探测了）
 *  	想象一下产生这种情况的场景：一个节点右左有右，现在删了其中一个，所以平衡因子是-1或1，但子树高度没变
 *  如果删除后，父节点的平衡因子=0，说明之前的高度差是1，现在是0，虽然是平衡的，但高度差变了，需要继续往上探测
 *		想象一下产生这种情况的场景：一个节点只有左或右，现在删了，变成0了，子树高度变了（-1），所以要继续往上探测父节点
 * 右旋（右旋会降低左子树高度）：
 * 	1 节点的原左节点作为新根
 *  2 节点作为新根的右节点
 *  3 原左节点的右节点，变为节点的左节点
 *  4 旋转之后，新根和节点的平衡因子均置零
 * 左旋（左旋会降低右子树高度）：
 * 	1 节点的右节点作为新根
 *  2 节点作为新根的左节点
 *  3 原右节点的左节点，变为节点的右节点
 *  4 旋转之后，新根和节点的平衡因子均置零
 *
 * @author ala
 * @date 2025年5月17日
 */
public class AVLLinked<K, V> extends AbstractTree<K, V> {

	
	protected Node HEAD;
	
	public AVLLinked(Comparator<K> comparator) {
		super(comparator);
	}

	@Override
	public boolean add(K k, V v) {
		if (size == 0) {
			HEAD = new Node(k, v);
			size++;
			return true;
		}
		if (_add(HEAD, new Node(k, v))) {size++;}
		return true;
	}
	protected boolean _add(Node r, Node n) {
		int c = comparator.compare(n.key, r.key);
		//	不允许重复插入（其实重复插入应该执行update）
		if (c == 0) {return false;}
		else if (c < 0) {
			//	如果此时r.left就是空，那就是n的插入点
			if (r.left == null) {
				r.left = n; n.parent = r;
				//	尝试旋转
				tryRotationAdd(r, n, 1);
				return true;
			} 
			//	如果r.left没坑，继续递归
			else {
				return _add(r.left, n);
			}
		} else {
			//	如果此时r.right为空，那就是n的插入点
			if (r.right == null) {
				r.right = n; n.parent = r;
				//	尝试旋转
				tryRotationAdd(r, n, 1);
				return true;
			} 
			//	如果r.right没坑，继续递归
			else {
				return _add(r.right, n);
			}
		}
	}
	/**
	 * 	尝试旋转
	 */
	protected void tryRotationAdd(Node r, Node n, int d) {
		if (r == null) {return;}
		//	更新r的bf
		if (r.left == n) {r.bf -= d;}
		else {r.bf += d;}
		
		//	如果r的左右是完全平衡的，说明到r这就截止了
		if (r.bf == 0) {return;}
		//	如果r的平衡因子变化后是[-1, 1]，说明变之前是完全平衡的。现在高度差变了，连带着父节点也要变
		else if (r.bf == -1 || r.bf == 1) {
			tryRotationAdd(r.parent, r, d);
		} 
		//	如果r现在是不平衡的，那先要对r进行旋转
		else {
			//	如果是左子树不平衡
			if (r.bf == -2) {
				//	如果不平衡来自左子树的左子树，右旋
				if (n.bf == -1) {
					rotationR(r);
				}
				//	如果不平衡来自左子树的右子树，先对左子树左旋，再自己右旋
				if (n.bf == 1) {
					rotationL(r.left);
					rotationR(r);
				}
			} else {
				//	如果不平衡来自右子树的右子树，左旋
				if (n.bf == 1) {
					rotationL(r);
				}
				//	如果不平衡来自右子树的左子树，右子树右旋，自己再左旋
				if (n.bf == -1) {
					rotationR(r.right);
					rotationL(r);
				}
			}
		}
	}
	/**
	 * 	右旋转
	 * 	1）n.right = r
	 *  2）r.left = n.right
	 *  3）n变成新的r
	 */
	protected void rotationR(Node r) {
		Node p = r.parent, n = r.left;
		//	1）n.right = r  2）r.left = n.right
		Node nr = n.right;
		n.right = r;
		r.left = nr; r.parent = n;
		//	3）n变成新的r
		if (p != null) {
			if (r == p.left) {p.left = n;}
			else {p.right = n;}
			n.parent = p;
		} else {
			HEAD = n;
			n.parent = null;
		}
		//	旋转之后r和n的平衡因子都是0
		r.bf = n.bf = 0;
	}
	/**
	 * 	左旋转
	 * 	1）n.left = r
	 *  2）r.right = n.left
	 *  3）n变成新的r
	 */
	protected void rotationL(Node r) {
		Node p = r.parent, n = r.right;
		//	1）n.left = r  2）r.right = n.left
		Node nl = n.left;
		n.left = r;
		r.right = nl; r.parent = n;
		//	3）n变成新的r
		if (p != null) {
			if (r == p.left) {p.left = n;}
			else {p.right = n;}
			n.parent = p;
		} else {
			HEAD = n;
			n.parent = null;
		}
		//	旋转之后r和n的平衡因子都是0
		r.bf = n.bf = 0;
	}

	
	@Override
	public boolean remove(K k) {
		if (size == 0) {return false;}
		if (size == 1) {
			if (comparator.compare(k, HEAD.key) == 0) {
				size = 0;
				HEAD = null;
				return true;
			}
			return false;
		}
		if (_remove(HEAD, k)) {size--;}
		return true;
	}
	protected boolean _remove(Node r, K k) {
		if (r == null) {return false;}
		int c = comparator.compare(k, r.key);
		if (c == 0) {_remove(r); return true;}
		else if (c < 0) {return _remove(r.left, k);}
		else {return _remove(r.right, k);}
	}
	protected void _remove(Node n) {
		Node p = n.parent;
		//	如果删除的是叶子节点，直接删，删了后做调整
		if (n.left == null && n.right == null) {
			//	左右子树都为空，删除的还是根节点，那直接清空
			if (p == null) {
				HEAD = null;
			} else {
				if (p.left == n) {
					p.left = null;
					tryRotationRemove(p, true);
				} else {
					n.parent.right = null;
					tryRotationRemove(p, false);
				}
			}
		} 
		//	如果删除节点只有左子树或右子树，拿子节点做当前节点，删了后做调整
		else if (n.right == null || n.left == null){
			Node sub = n.right == null ? n.left : n.right;
			//	删除的是根节点，直接把唯一的子节点提到根节点上
			if (p == null) {
				HEAD = sub;
			} else if (p.left == n) {
				p.left = sub; sub.parent = p;
				tryRotationRemove(p, true);
			} else {
				p.right = sub; sub.parent = p;
				tryRotationRemove(p, false);
			}
		}
		//	如果删除节点包含左右子树，找到中序遍历的下一个节点，用该节点替换当前待删节点，删除节点改为中序后继节点
		//	中序后继一定是叶子节点或只有1个子节点）
		//	删了后做调整
		else {
			Node nxt = inorderTraversal(n.key);
			n.key = nxt.key; 
			n.val = nxt.val;
			_remove(nxt);
		}
	}
	/**
	 * 中序遍历的下个节点
	 */
	protected Node inorderTraversal(K k) {
		Node crt = HEAD;
		LinkedList<Node> stack = new LinkedList<>();
		boolean find = false;
		while (crt != null || !stack.isEmpty()) {
			while (crt != null) {
				stack.addLast(crt);
				crt = crt.left;
			}
			crt = stack.poll();
			if (find) {return crt;}
			if (comparator.compare(k, crt.key) == 0) {find = true;}
			
			crt = crt.right;
		}
		return null;
	}
	/**
	 * 	因为删除带来的调整
	 */
	protected void tryRotationRemove(Node n, boolean left) {
		if (n == null) {return;}
		//	于插入时刚好相反，左+右-
		n.bf += left ? 1 : -1;
		
		//	如果调整完，平衡因子是-1或1，说明之前是0（平衡的），现在还是平衡的，无需继续向上调整
		if (n.bf == -1 || n.bf == 1) {
			return;
		} 
		//	如果调整完，平衡因子是0，说明之前是-1或1，现在是0，高度差发生了变化，需要继续向上调整
		else if (n.bf == 0) {
			Node p = n.parent;
			if (p != null) { tryRotationRemove(p, p.left == n); }
		}
		//	如果调整完，平衡因子是-2或2，说明当前是不平衡的，需要调整。并且需要继续向上调整
		else {
			//	如果是左子树高
			if (n.bf == -2) {
				Node l = n.left;
				//	如果原先就是平衡的，或不平衡来自左子树的左子树，右旋
				if (l.bf <= 0) {
					rotationR(n);
				}
				//	不平衡来自左子树的右子树，左子树左旋，自己右旋
				if (l.bf == 1) {
					rotationL(l);
					rotationR(n);
				}
			} 
			//	如果右子树高
			else {
				Node r = n.right;
				//	如果原先就是平衡的，或不平衡来自右子树的右子树，左旋
				if (r.bf >= 0) {
					rotationL(n);
				}
				//	如果不平衡来自右子树的左子树，右子树右旋，自己左旋
				if (r.bf == -1) {
					rotationR(r);
					rotationL(n);
				}
			}
		}
	}
	

	@Override
	public boolean update(K k, V v) {
		Node n = _search(HEAD, k);
		if (n == null) {return false;}
		n.val = v;
		return true;
	}

	@Override
	public V search(K k) {
		Node n = _search(HEAD, k);
		return n == null ? null : n.val;
	}
	protected Node _search(Node r, K k) {
		if (r == null) {return null;}
		int c = comparator.compare(k, r.key);
		if (c == 0) {return r;}
		else if (c < 0) {return _search(r.left, k);}
		else {return _search(r.right, k);}
	}
	
	@Override
	public String toString() {
		StringBuilder sbuf = new StringBuilder();
		postOrder(HEAD, 0, sbuf);
		return sbuf.toString();
	}
	protected void postOrder(Node r, int level, StringBuilder sbuf) {
		if (r == null) {return ;}
		StringBuilder t = new StringBuilder();
		for (int l = 0 ; l < level ; l++) {t.append("\t");}
		String l = " H";
		if (r.parent != null) {
			if (r.parent.left == r) {l = " L";}
			else {l = " R";}
		}
		sbuf.append(t).append(String.format("(%s,%d)", r.key, r.bf)).append(l).append("\n");
		postOrder(r.left, level+1, sbuf);
		postOrder(r.right, level+1, sbuf);
	}

	/**
	 * 	节点
	 */
	public class Node {
		K key;
		V val;
		Node parent, left, right;
		//	平衡因子：(-1,0,1)
		int bf;
		public Node(K k, V v) {key = k; val = v;}
		public String toString() {
			return String.format("(%s,%d)", val, bf);
		}
	}
	
}
